//
//  RSMath.m
//  RSMath
//
//  Copyright (c) 2007-2009 Raphael Sobik. All rights reserved.
//
//  Redistribution and use in source and binary forms, with or without
//  modification, are permitted provided that the following conditions are met:
//  1. Redistributions of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//  2. Redistributions in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation
//     and/or other materials provided with the distribution.
//  3. The name of the author may not be used to endorse or promote products
//     derived from this software without specific prior written permission.
//
//  THIS SOFTWARE IS PROVIDED BY Raphael Sobik "AS IS" AND ANY EXPRESS
//  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
//  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
//  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
//  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
//  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
//  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
//  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
//  OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
//  EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//

#import "RSMath.h"


@implementation RSMath

+ (RSNumber *)gcdOf:(RSNumber *)a and:(RSNumber *)b
{
	RSNumber *temp;
	while(![b isZero])
	{
		temp = a;
		a = b;
		b = [temp mod:b];
	}
	return [a copy];
}

+ (NSArray *)extendedEuclidianAlgorithmOf:(RSNumber *)a and:(RSNumber *)b
{
	if([b isZero])
		return [NSArray arrayWithObjects:a, [RSNumber numberWithInteger:1], [RSNumber numberWithInteger:0], nil];
	NSArray *st_temp = [self extendedEuclidianAlgorithmOf:b and:[a mod:b]];
	RSNumber *s = [st_temp objectAtIndex:2];
	
	RSNumber *temp = [[a divideWith:b] multiplyWith:[st_temp objectAtIndex:2]];
	RSNumber *t = [[st_temp objectAtIndex:1] subtract:temp];
	return [NSArray arrayWithObjects:[st_temp objectAtIndex:0], s, t];
}

+ (NSArray *)primesUpto:(RSNumber *)maxPrime
{
    RSNumber *i = [RSNumber numberWithInteger:2];
    RSNumber *one = [RSNumber numberWithInteger:1];
    NSMutableArray *primes = [NSMutableArray array];
    
    [primes addObject:[RSNumber numberWithInteger:2]];
    
    while ([i isSmallerThan:maxPrime])
    {
        if ([i isPrime])
        {
            [primes addObject:i];
        }
        i = [i add:one];
    }
    return [primes copy];
}

@end
